//在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（
//上下左右）进行交换. 
//
// 最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。 
//
// 给出一个谜板的初始状态 board ，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：board = [[1,2,3],[4,0,5]]
//输出：1
//解释：交换 0 和 5 ，1 步完成
// 
//
// 示例 2: 
//
// 
//
// 
//输入：board = [[1,2,3],[5,4,0]]
//输出：-1
//解释：没有办法完成谜板
// 
//
// 示例 3: 
//
// 
//
// 
//输入：board = [[4,1,2],[5,0,3]]
//输出：5
//解释：
//最少完成谜板的最少移动次数是 5 ，
//一种移动路径:
//尚未移动: [[4,1,2],[5,0,3]]
//移动 1 次: [[4,1,2],[0,5,3]]
//移动 2 次: [[0,1,2],[4,5,3]]
//移动 3 次: [[1,0,2],[4,5,3]]
//移动 4 次: [[1,2,0],[4,5,3]]
//移动 5 次: [[1,2,3],[4,5,0]]
// 
//
// 
//
// 提示： 
//
// 
// board.length == 2 
// board[i].length == 3 
// 0 <= board[i][j] <= 5 
// board[i][j] 中每个值都 不同 
// 
// Related Topics广度优先搜索 | 数组 | 矩阵 
//
// 👍 270, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class SlidingPuzzle {
    public static void main(String[] args) {
        Solution solution = new SlidingPuzzle().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int slidingPuzzle(int[][] board) {
            String target = "123450";   // 目标值
            int step = 0;
            Queue<String> queue = new LinkedList<>();
            Set<String> visited = new HashSet<>();

            // 将原始的board，生成开始的字符串
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < board.length; i++)
                for (int j = 0; j < board[0].length; j++)
                    sb.append(board[i][j]);
            String start = sb.toString();

            // 记录一维字符串的相邻索引
            int[][] neighbor = new int[][]{
                    {1, 3},
                    {0, 4, 2},
                    {1, 5},
                    {0, 4},
                    {3, 1, 5},
                    {4, 2}
            };

            // 开始BFS搜索
            queue.offer(start);
            visited.add(start);

            while (!queue.isEmpty()) {

                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    String cur = queue.poll();

                    if (cur.equals(target)) {
                        return step;
                    }

                    // 找到0所在的的索引
                    int index = 0;
                    for (; cur.charAt(index) != '0'; index++) ;

                    // 找到0相邻的索引进行搜索
                    for (int nextIndex : neighbor[index]) {
                        String new_board  = swap(cur.toCharArray(), index, nextIndex);
                        if (!visited.contains(new_board )) {
                            queue.offer(new_board );
                            visited.add(new_board );
                        }
                    }
                }

                step++;
            }

            return -1;
        }

        public String swap(char[] arr, int i, int j) {
            char temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            return new String(arr);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
